import sys

try:
    t = int(input())
    if t < 1 or t > 100:
        sys.exit(0)
    for t in range(t):
        n, m = list(map(int, input().split()))
        a = [int(item) for item in input().split()]
        temp = [a[0]]
        for i in range(1,n):
            temp.append((2*temp[i-1]+a[i])%m)
        sumN = [2*a[0]-1]
        for i in range(1,n):
            if a[i]==1:
                sumN.append((2*temp[i-1]%m+1)%m)
            else:
                sumN.append((2*temp[i-1]%m+2*a[i]+sumN[i-1])%m)
        print(sumN[-1])

except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass